#include <iostream>
#include <cstring>
#include <algorithm>
#define add(a,b) ((a)+(b)>=mod?(a)+(b)-mod:(a)+(b))
#define int long long
using namespace std;

namespace fastio{
    struct{template<typename T>operator T(){
        T x=0;char f=0,c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
        return f?-x:x;
    }}in;int stk[40],tp;
    template<typename T>void out(T x,char c=0){
        if(x<0)putchar('-'),x=-x;
        do stk[++tp]=x%10,x/=10;while(x);
        while(tp)putchar(stk[tp--]^48);
        if(c)putchar(c);
    }
}using fastio::in;using fastio::out;

const int N = 2005,M = N*N;
int f[2][M],g[M];
int n,m,mod;

int ksm(int a,int b){
    int ans = 1;
    while(b){
        if(b&1)
            ans = ans*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}

signed main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    mod = in;
    int t = in;
    while(t--){
        n = in,m = in;
        memset(f[0],0,sizeof(int)*(n*m+1));
        memset(f[1],0,sizeof(int)*(n*m+1));
        int o = 0,p = ksm(m+1,mod-2);
        f[o][0] = 1;
        for(int k=1;k<=n;k++){
            memset(f[o^1],0,sizeof(int)*(k*m+1));
            g[0] = f[o][0];
            for(int j=1;j<=k*m;j++)
                g[j] = add(g[j-1],f[o][j]);
            for(int j=0;j<=k*m;j++)
                f[o^1][j] = (g[j]-(j-m-1>=0?g[j-m-1]:0)+mod)*p%mod;
            o ^= 1;
        }
        int ans = 0,sum = 0;
        for(int k=0;k<=n*m;k++){
            ans = (ans+f[o][k]*sum)%mod;
            sum = add(sum,f[o][k]);
        }
        out(ans,'\n');
    }
    return 0;
}